import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description：
 * User：user
 * DATE:2021-11-11
 * Time:11:07
 */
public class TestDemo {

    public int lastStoneWeight(int[] stones) {

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int tmp:stones) {
            maxHeap.offer(tmp);
        }

        while (maxHeap.size() > 1){
            int a = maxHeap.poll();
            int b = maxHeap.poll();
            if(a > b){
                maxHeap.offer(a - b);
            }
        }
        return maxHeap.isEmpty()?0:maxHeap.poll();

    }















    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> ret = new ArrayList<>();

        //和最小的k个数字
        PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o2.get(0) + o2.get(1)) - (o1.get(0) + o1.get(1));
            }
        });

        for (int i = 0; i < Math.min(k,nums1.length); i++) {
            for (int j = 0; j < Math.min(k,nums2.length); j++) {
                if(maxHeap.size() < k){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    maxHeap.offer(list);
                }else{
                    List<Integer> top = maxHeap.peek();
                    int val = top.get(0) + top.get(1);
                    if(val > nums1[i] + nums2[j]){
                        List<Integer> list = new ArrayList<>();
                        list.add(nums1[i]);
                        list.add(nums2[j]);
                        maxHeap.offer(list);
                    }
                }
            }
        }
        for (int i = 0; i < k && !maxHeap.isEmpty(); i++) {
            List<Integer> tmp = maxHeap.poll();
            ret.add(tmp);
        }
        System.out.println(ret);

    }


    //最好 平均时间复杂度：O（N*log2N每次都能够均匀的分割待排序的序列
    //最坏时间复杂度：O（N*log2N）有序
    //最好 平均 空间复杂度:log2N
    //最坏时间复杂度：O(n)
    public static  int partion(int[] array, int start,int end){
        int tmp = array[start];
        while (start < end){
            while (start < end && array[end] >= tmp){
                end--;
            }
            array[start] = array[end];
            while (start < end && array[start] <= tmp){
                start++;
            }
            array[start] = tmp;
            return  start;
        }
    }


    public static void quick(int[] array,int low,int high){
        if(low >= high){
            return;
        }
        int pivot = partion(array,low,high);
        quick(array,low,pivot - 1);
        quick(array,pivot + 1,high);
    }
    public  static  void  quicKSort(int[] array){

    }

    //时间复杂度：O(N^2)  优化的有序情况下时间复杂度为O（n）；
    //空间复杂度：O(1)
    //稳定的排序  也可以变成不稳定的排序
    public static void bubleSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = true;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if(array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j]  = array[j+1];
                    array[j + 1] = tmp;
                    flag  = false;
                }
            }
            if(flag == true){
                break;
            }
        }
    }

    //堆排序
    //首先要建立大根堆 最后一棵子树开始向下调整每棵子树
    //第一个元素和最后一个元素交换之后在进行排序
    //时间复杂度：O（nlog2n）
    //空间复杂度：O（1）
    //不稳定
    public static  void heapSort(int[] array){
        createHeap(array);
       int end = array.length - 1;
       while (end > 0){
           int tmp = array[end];
           array[end] = array[0];
           array[0]  = tmp;
           shiftDown(array,0,end);
           end--;
       }
    }
    public  static void shiftDown(int[] array,int parent,int len){
        int child = 2 * parent + 1;
        while (child < len){
            if(child + 1 < len && array[child] < array[child + 1]){
                child++;
            }
            if(array[child] > array[parent]){
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
                parent = child;
                child = 2 * parent + 1;
            }else{
                break;
            }
        }
    }
    public  static  void createHeap(int[] array){
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(array,parent,array.length);
        }

    }

    public static void main(String[] args) {
        int[] array = {4,5,8,2};
        bubleSort(array);
        System.out.println(Arrays.toString(array));
    }

    //选择排序
    //每个位置放上最小的元素 每趟放一个元素
    //时间复杂度为：O(n^2)
    //空间复杂度为O（1）
    //稳定性：不稳定的排序
    public static  void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if(array[j] < array[i]){
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }

    }

    public static void main11(String[] args) {
        int[] array = new int[10_0000];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(10_0000);
        }
        long start = System.currentTimeMillis();
        selectSort(array);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }
    public static void main9(String[] args) {
        int[] array = {9,5,4};
        selectSort(array);
        System.out.println(Arrays.toString(array));

    }



    //希尔排序是直接插入元素的优化
    //对数据进行分组在进行直接插入排序，可以降低时间复杂度
    //时间复杂度O（N^1.3 ---- N^1.5）
    public  static  void shellSort(int[] array){
        int[] drr = {5,3,1};//不好求 有10000个数据也是5 3 1 吗？
        for (int i = 0; i < drr.length; i++) {
            shell(array,drr[i]);
        }
    }

    public  static  void shellSort1(int[] array){
        int gap = array.length;
        while (gap > 1){
            shell(array,gap);
            gap = (gap / 3) + 1;
        }
        shell(array,1);
    }
    public  static  void shell(int[] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j = j - gap) {
                if(array[j] > tmp){
                    array[j + gap] = array[j];
                }else{
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }
    public static void main8(String[] args) {
        int[] array = {4,5,8,2};
        shellSort(array);
        System.out.println(Arrays.toString(array));
    }


    public static void main7(String[] args) {
        int[] array = {4,5,8,2};
        //有序块 无序块  每次从无序块中取出元素放入到有序块中
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j =  i - 1;
            for (; j >= 0 ; j--) {
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
        System.out.println(Arrays.toString(array));
    }



    //直接插入排序
    //时间复杂度最坏情况下为O（N^2） 逆序每次都需要交换
    //最好情况下的时间复杂度为O（n）; 越有序越快
    //稳定性：稳定的 也可变为不稳定的  一个稳定的排序可以变为不稳定的排序，一个不稳定的排序是不可能变成稳定的排序
    //技巧：如何快速判断一个排序是否稳定 是否有发生跳跃式的交换  j 给 j + 5 跳跃式不是稳定性的交换
    //稳定性表示的是排序前两个相同的数字相对位置和排序后的两个相同数字相对位置相同
    //空间复杂度：O（1）
    public static void main6(String[] args) {
        int[] array = {5,1,10};
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j =  i - 1;
            for (; j >= 0; j--) {
                if(array[j] > tmp){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
        System.out.println(Arrays.toString(array));
    }


    public static void main5(String[] args) {
        int[] array = {9,8,10,20,30};
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0 ; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
        System.out.println(Arrays.toString(array));
    }

    public static void main4(String[] args) {
        int[] array = {5,10,20,3,90};
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if(array[j] > tmp){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1 ] = tmp;
        }
        System.out.println(Arrays.toString(array));
    }

    public static void main3(String[] args) {
        int[] array = {5,9,8,1,20};
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j =  i - 1;
            for (; j >= 0; j--) {
                if(array[j] > tmp){
                    array[j + 1 ] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
        System.out.println(Arrays.toString(array));
    }

    public static void main2(String[] args) {
        int[] array = {4,9,10,90,2};
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else {
                    array[j+1] = tmp;
                    break;
                }
            }
            array[j + 1] = tmp;
        }
        System.out.println(Arrays.toString(array));
    }
    public static void main1(String[] args) {
        int[] array = {1,5,8,91,10};
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (;j >= 0; j--){
                if(array[j] > tmp){
                    array[j + 1]  = array[j];
                }else{
                    //array[j + 1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
        System.out.println(Arrays.toString(array));
    }
}
